/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/word-break
   @Language: C++
   @Datetime: 19-11-18 16:27
   */

// Method 1, dp, Time O(n*k), Space O(n+m+k)
// dp[i] means : 0~i can be split
class Solution {
public:
	bool wordBreak(string s, vector<string>& words) {
		unordered_set<string> dict(words.begin(),words.end());
		unordered_set<int> lens;
		for(const string &word:dict)
			lens.insert(word.length());
		vector<bool> dp(s.length()+1,false);
		dp[0]=true;
		for(int i=1; i<=s.length(); ++i){
			for(const int &l:lens){
				if(i>=l && dp[i-l] && dict.count(s.substr(i-l,l))){
					dp[i]=true;
					break;
				}
			}
		}
		return dp[s.length()];
	}
};
